import java.util.Scanner;

public class Fibo {
    public static void main(String[] args) {
        long[] arr = new long[1000000];
        arr[0] = 1;
        arr[1] = 2;
        int border = -1;
        long next = 0;
        for(int i = 2; i < 1000000; i++) {
            next = arr[i - 1] + arr[i - 2];
            if(border == -1 && next >= 1000000) {
                border = i + 1;
            }
            arr[i] = next % 1000000;
        }
        Scanner s = new Scanner(System.in);
        while(s.hasNextInt()) {
            int n = s.nextInt();
            long f = arr[n - 1];
            if(n < border) {
                System.out.printf("%d\n",f);
            }else {
                System.out.printf("%06d\n",f);
            }
        }
    }
}
